// 81. 搜索旋转排序数组 II
// https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/description/
// 二分法
// 这题不能用二分法，做不出来的
/**
示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true
示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

 */

// 思路
// 暴力解就可以

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {boolean}
 */
var search = function (nums, target) {
    // 这个数组的特点是，中间有一个极小值，所以从两头开始搜会准确点

    if (nums[0] === target || nums[nums.length - 1] === target) return true;

    // 至于从那一头，看target
    const len = nums.length - 1;
    const headNum = nums[0];

    if (target < headNum) {
        // 从后往前
        // 如果突然某个数比头还大，那就进第二个数组了，可以退出
        for (let i = len; i >= 0; i--) {
            if (nums[i] === target) return true;
            if (nums[i] > headNum) return false;
        }
    } else {
        // 从前往后
        // 如果突然某个数比头还小，那就不用找了，退出
        for (let i = 0; i <= len; i++) {
            if (nums[i] === target) return true;
            if (nums[i] < headNum) return false;
        }
    }

    return false;
};

var findSplit = function () {
    // 逻辑
    // 二分法推演不下去了。。。。
    // 分界点元素，那其实会分成arr_1和arr_2两个数组，其中：arr_2的每个元素都 >= arr_1
    // 即:
    // arr = [arr_2[0], ..., arr_2[max], arr_1[0], ...arr_1[max]]
    // 如果二分的元素X
    // X <= arr_2[0],right = center [1201111] [111111201]
    // X > arr_2[0],left = center [2221]
};
